#include <iostream>
#include <vector>

using namespace std;

/*
在二元树中找出和为某一值的所有路径
题目:输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22 和如下二元树
        10
        /\
        5 12
       /\
      4  7
则打印出两条路径:10, 12 和10, 5, 7
*/

struct TreeNode {
    int val;
    TreeNode* lchild;
    TreeNode* rchild;
};

TreeNode* buildTree() {
    TreeNode* head = NULL;
    TreeNode *n1, *n2, *n3, *n4;

    n3 = new TreeNode();
    n3->val = 4;
    n3->lchild = n3->rchild = NULL;

    n4 = new TreeNode();
    n4->val = 7;
    n4->lchild = n4->rchild = NULL;


    n1 = new TreeNode();
    n1->val = 5;
    n1->lchild = n3;
    n1->rchild = n4;

    n2 = new TreeNode();
    n2->val = 12;
    n2->lchild = n2->rchild = NULL;
    
    head = new TreeNode();
    head->val = 10;
    head->lchild = n1;
    head->rchild = n2;

    return head;
}

void PrintPath(vector<TreeNode *> path) {
    typedef vector<TreeNode *>::iterator IT;
    for (IT it = path.begin(); it != path.end(); it++)
        cout << (*it)->val << " ";
    cout << endl;
}

void FindPathRecursively(TreeNode* pNode, int leftsum, vector<TreeNode*>& path) {
    if (pNode == NULL) return;

    leftsum -= pNode->val;
    path.push_back(pNode);

    if (leftsum < 0)
        ;
    else if (leftsum == 0) {// Find one path, print it.
        PrintPath(path);
    } else {
        FindPathRecursively(pNode->lchild, leftsum, path);
        FindPathRecursively(pNode->rchild, leftsum, path);
    }

    path.pop_back();
}

int main() {
    TreeNode* root;
    root=  buildTree();

    vector<TreeNode *> path;
    FindPathRecursively(root, 22, path); 
    

}

